package patchingArray;



public class Solution {
    public int minPatches(int[] nums, int n) {
        int ans=0,begin=0;
        long max=0;

        for (int i=begin;i<nums.length;i++){
        	if (nums[i]<=max+1)
        		{
        		  max=max+nums[i];
        		  if (max>=n) return ans;
        		}
        	else{
        		while (max+1<nums[i]){
        			max=max+max+1;
        			ans++;
        			if (max>=n) return ans;
        		}
        		max=max+nums[i];
        		if (max>=n) return ans;
        	}
        }
        while (max<n){
        	max=max+max+1;
        	ans++;
        }
        return ans;
    }
	public static void main(String args[]){
		Solution so=new Solution();
		int[] nums={1};
		System.out.println(so.minPatches(nums, 10));
		}
	
}
/* 
 * 330. Patching Array
 * 题目大意：给定一个有序数组，问添加几个数能使这个数组内的数表达出0~n中每个数
 * O（n）
 * 贪心+分治
 * 对数组中第i个位置的数，维护一个max表示可以表示[0，max]中的每个数用添加ans个数的代价达成
 * 
 * 阶段最优性证明（贪心核心）：
 * ∵若要证明nums[i]的加入破坏之前的阶段最优性，则需nums[i]等于之前添加到数组中的某个数
 * 然  
 * ∵数组有序 
 * ∴nums[t]<=nums[i](t<i)
 * ∴nums[i]只有可能等于nums数组末位置的数
 * 故证明得证
 * 
 * 添加（max+1）的最优性证明
 * ∵当0~max无法达成n的要求时
 * 决策I 加入数组下一个数nums[i]（需满足nums[i]<=max+1,保证连续性，添加后范围变为0~nums[i]+max）
 * 决策II ans++，并选择一个数加入
 * ∵此时的连续范围为0~max
 * ∴加入的数需保证范围变得尽量大且连续
 * ∴加入的数为max+1，连续范围变为0~2*max+1
 * 
 * PS:细节，当max大于n时直接返回ans
 */